package com.zhouxianglh.p10;

/**
 * 10. 正则表达式匹配
 * <p>
 * 注意,正则表达式有歧义性.动态规划使用数组保存中间结果,可以极大的提高性能!!!
 *
 * @author zhouxianglh
 */
public class Solution {
    public static void main(String[] args) {
        // System.out.println(isMatch("aa", "a"));//false
        // System.out.println(isMatch("aa", "a*"));//true
        // System.out.println(isMatch("ab", ".*"));//true
        // System.out.println(isMatch("aab", "c*a*b"));//true
        // System.out.println(isMatch("mississippi", "mis*is*p*."));//false
        // System.out.println(isMatch("a", ""));//false
        // System.out.println(isMatch("ab", ".*c"));//false
        // System.out.println(isMatch("aaa", "a*a"));//true
        // System.out.println(isMatch("a", "ab*"));//true
        System.out.println(isMatch("bbbba", ".*a*a"));//true
    }

    public static boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        return check(s, 0, p, 0);
    }

    public static boolean check(String s, int sIndex, String p, int pIndex) {
        if (sIndex == s.length()) {
            if (pIndex == p.length()) {
                return true;
            } else if (pIndex < p.length()) {
                boolean isMany = p.length() > (pIndex + 1) && p.charAt(pIndex + 1) == '*';
                if (isMany) {
                    return check(s, sIndex, p, pIndex + 2);
                } else {
                    return false;
                }
            }
        } else if (sIndex < s.length()) {
            if (pIndex == p.length()) {
                return false;
            }
        }
        boolean isPoint = p.charAt(pIndex) == '.';
        boolean isMany = p.length() > (pIndex + 1) && p.charAt(pIndex + 1) == '*';
        char c = s.charAt(sIndex);
        if (isMany) {
            if (isPoint || c == p.charAt(pIndex)) {
                if (check(s, sIndex + 1, p, pIndex)) {
                    return true;
                }
                if (check(s, sIndex + 1, p, pIndex + 2)) {
                    return true;
                }
            }
            return check(s, sIndex, p, pIndex + 2);
        } else {
            if (isPoint) {
                return check(s, sIndex + 1, p, pIndex + 1);
            } else if (c == p.charAt(pIndex)) {
                return check(s, sIndex + 1, p, pIndex + 1);
            } else {
                return false;
            }
        }
    }
}
